#include <stdio.h>
#include <stdlib.h>

#include "LinkList.h"

Status InitList(LinkList *L)
{
    (*L) = (LinkList) malloc(sizeof(LNode));    
    
    if ((*L) == NULL)
    {
        return OVERFLOW;
    }

    (*L)->next = NULL;

    return OK;
}


Status DestroyList(LinkList* L)
{
    LinkList temp;

    if (L == NULL || (*L) == NULL)
    {
        return ERROR;
    }

    temp = *L;
    while (temp)
    {
        temp = (*L)->next;
        free(*L);
        (*L) = temp;
    }

    (*L) = NULL;    

    return OK;

}


Status ClearList(LinkList L)
{
    LinkList temp;
    if (L->next == NULL)
    {
        return ERROR;
    }

    temp = L->next;

    while (temp)
    {
        temp = L->next->next;
        free(L->next);
        L->next = temp;
    }

    return OK;
        
}

/*
 * 判空
 *
 * 判断链表中是否包含有效数据。
 *
 * 返回值：
 * TRUE : 链表为空
 * FALSE: 链表不为空
 */
Status ListEmpty(LinkList L);

/*
 * 计数
 *
 * 返回链表包含的有效元素的数量。
 */
int ListLength(LinkList L);

/*
 * ████████ 算法2.8 ████████
 *
 * 取值
 *
 * 获取链表中第i个元素，将其存储到e中。
 * 如果可以找到，返回OK，否则，返回ERROR。
 *
 *【备注】
 * 教材中i的含义是元素位置，从1开始计数，但这不符合编码的通用约定。
 * 通常，i的含义应该指索引，即从0开始计数。
 */
Status GetElem(LinkList L, int i, ElemType* e)
{
    LinkList temp;
    int j = 0;

    if (L->next == NULL)
    {
        return ERROR;
    }

    temp = L;

    for ( j = 0; j <= i && temp != NULL; j++)
    {
        temp = temp->next;
    }
    
    if (temp == NULL || j > i+1)
    {
        return ERROR;
    }
    
    *e = temp->elem;
    return OK;
}

/*
 * 查找
 *
 * 返回链表中首个与e满足Compare关系的元素位序。
 * 如果不存在这样的元素，则返回0。
 *
 *【备注】
 * 元素e是Compare函数第二个形参
 */
int LocateElem(LinkList L, ElemType e, Status(Compare)(ElemType, ElemType));

/*
 * 前驱
 *
 * 获取元素cur_e的前驱，
 * 如果存在，将其存储到pre_e中，返回OK，
 * 如果不存在，则返回ERROR。
 */
Status PriorElem(LinkList L, ElemType cur_e, ElemType* pre_e);

/*
 * 后继
 *
 * 获取元素cur_e的后继，
 * 如果存在，将其存储到next_e中，返回OK，
 * 如果不存在，则返回ERROR。
 */
Status NextElem(LinkList L, ElemType cur_e, ElemType* next_e);

/*
 * ████████ 算法2.9 ████████
 *
 * 插入
 *
 * 向链表第i个位置上插入e，插入成功则返回OK，否则返回ERROR。
 *
 *【备注】
 * 教材中i的含义是元素位置，从1开始计数
 */
Status ListInsert(LinkList L, int i, ElemType e)
{
    int j;
    LinkList temp,node;
    temp = (LNode *)malloc(sizeof(LNode));

    if (temp == NULL)
    {
        return ERROR;
    }

    node = L;

    for ( j = 0; j < i; j++)
    {
        node = node->next;
    }
    
    temp->elem = e;
    temp->next = node->next;
    node->next = temp;

    return OK;
}

/*
 * ████████ 算法2.10 ████████
 *
 * 删除
 *
 * 删除链表第i个位置上的元素，并将被删除元素存储到e中。
 * 删除成功则返回OK，否则返回ERROR。
 *
 *【备注】
 * 教材中i的含义是元素位置，从1开始计数
 */
Status ListDelete(LinkList L, int i, ElemType* e)
{
    LinkList pre,delnode;
    int j=0;
    // 校验链表是否初始化或者为空
    if (L == NULL || L->next == NULL)
    {
        return ERROR;
    }
    
    pre = L;
    //是pre指向被删除节点的前驱节点
    while (L->next != NULL && j<i)
    {
        pre = pre->next;
        j++;
    }

    //校验i输入是否合法，i不能小于0(j>i)，不能大于链表的最大索引(pre->next == NULL)
    if (pre->next == NULL || j>i)
    {
        return ERROR;
    }

    delnode = pre->next;    
    pre->next = delnode->next;

    *e = delnode->elem;
    free(delnode);

    return OK;
}

/*
 * 遍历
 *
 * 用visit函数访问链表L
 */
void ListTraverse(LinkList L, void(Visit)(ElemType))
{
    LinkList temp;

    temp = L->next;

    while (temp != NULL)
    {
        Visit(temp->elem);
        temp = temp->next;
    }
    printf("\n");
}

/*
 * ████████ 算法2.11 ████████
 *
 * 头插法创建链表
 *
 *
 *【备注】
 *
 * 教材中默认从控制台读取数据。
 * 这里为了方便测试，避免每次运行都手动输入数据，
 * 因而允许选择从预设的文件path中读取测试数据。
 *
 * 如果需要从控制台读取数据，则path为NULL或者为空串，
 * 如果需要从文件中读取数据，则需要在path中填写文件名信息。
 */
Status CreateList_Head(LinkList* L, int n)
{
    int i;
    LinkList temp;
    (*L) = (LinkList) malloc(sizeof(LNode));

    (*L)->next = NULL;

    for ( i = 0; i < n; i++)
    {
        temp = (LinkList) malloc(sizeof(LNode));

        scanf("%d",&temp->elem);


        temp->next =  (*L)->next;
        (*L)->next = temp;
    }
    
    return OK;
}

/*
 * 尾插法创建链表
 *
 *
 *【备注】
 *
 * 教材中默认从控制台读取数据。
 * 这里为了方便测试，避免每次运行都手动输入数据，
 * 因而允许选择从预设的文件path中读取测试数据。
 *
 * 如果需要从控制台读取数据，则path为NULL或者为空串，
 * 如果需要从文件中读取数据，则需要在path中填写文件名信息。
 */
Status CreateList_Tail(LinkList* L, int n)
{
    int i;
    LinkList temp,lastnode;
    (*L) = (LinkList) malloc(sizeof(LNode));

    (*L)->next = NULL;
    lastnode = (*L);

    for ( i = 0; i < n; i++)
    {
        temp = (LinkList) malloc(sizeof(LNode));
        scanf("%d",&temp->elem);
        
        lastnode->next = temp;
        lastnode = lastnode->next;
    }
    
    return OK;
}
